-module(priority_queue).
-export([new/0, add/3, remove_smallest/1, smallest/1, size/1]).

-record
(
        state,
        {
                ordered_set = gb_sets:new(), 
                dictionary = dict:new()
        }
).

new() ->
        #state{}.
        
add(Key, Value, State) ->
        OrderedSet = State#state.ordered_set,
        Dictionary = State#state.dictionary,
	NewOrderedSet = gb_sets:add(Key, OrderedSet),
        NewDictionary = dict:append(Key, Value, Dictionary),
	State#state
	{
	        ordered_set = NewOrderedSet,
	        dictionary = NewDictionary
	}.

remove_smallest(State)
        when State#state.ordered_set == [] ->
                State;
                 
remove_smallest(State) ->
        OrderedSet = State#state.ordered_set,
        Dictionary = State#state.dictionary,
	{Smallest, NewOrderedSet} = gb_sets:take_smallest(OrderedSet),
	ValueList = dict:fetch(Smallest, Dictionary),
	[_Head, NewValueList] = ValueList,
	case NewValueList of
	        [] ->
	                NewDictionary = dict:delete(Smallest, Dictionary),
	                State#state
	                {
	                        ordered_set = NewOrderedSet,
	                        dictionary = NewDictionary
	                };
	        _ ->
	                NewDictionary = dict:store(NewValueList, Dictionary),
	                State#state
	                {
	                        dictionary = NewDictionary
	                }	                
	end.

size(State) ->
        Dictionary = State#state.dictionary,
        dict:size(Dictionary).

smallest(State) ->
        gb_sets:smallest(State#state.ordered_set).

